1. Field of the Invention
The present invention relates to a technique for extracting a local feature from an image, compares each image, and calculates a similarity degree.
2. Description of the Related Art
There is a technique to search an image similar to a query image from a database or the like using an image as a search query. For example, Japanese Patent Application Laid-Open No. 08-249349 discusses a method in which an image is divided into a plurality of blocks and an image feature amount of a block in the same position is compared to make a comparison of similarity between two images by using an image feature amount (representative color) of each block. However, in the method discussed in Japanese Patent Application Laid-Open No. 08-249349, it is difficult to determine that the similarity is high, for example, when images are compared before and after a specified object in an image are cut off, or the position of the object is changed is compared.
Thus, a method for comparing or searching an image using a local feature amount of an image (hereinafter, referred to as local feature amount) is discussed in Japanese Patent Application Laid-Open No. 09-44665, and C. Schmid and R. Mohr “Local gray value invariants for image retrieval”, IEEE trans. PAML, Vol. 10, No. 5, pp 530 to 535, 1997.
In these methods, first, a feature point which definitely represents a feature of the image is extracted from a luminance distribution or the like. (These feature points are extracted by referring to distribution information generated by differentiating the luminance distribution in an x direction and a y direction. Thus, many of the feature points appear at an edge on the luminance distribution). Next, a local feature amount concerning its feature point is calculated from a neighboring image value containing its feature point. A value referred to as a local feature amount, includes varieties such as a pixel value, a luminance value, a shape, and a texture pattern. When an image is compared, the local feature amount of each image is compared with each other.
First, with respect to a plurality of feature points extracted from two images to be compared, local feature amounts that each feature point possesses are compared. Thus, a combination of feature points of two images which show a similar local feature amount is determined. The combination of feature points has a relation of 1:1. Then, similarity of two images is determined based on whether the degree of geometrical correspondence is satisfied as to the combination of feature points.
In a case where a size of an image is reduced, as to images before and after reduction, a position (or presence or absence) of a feature point extracted from the same location, or a value of a local feature amount concerning its feature point may fluctuate. It is desired that similarity with a query image can be determined as to an image containing a reduced content of an object included in a query image. Thus, both comparison target images are subjected to stepwise reduction conversion with a predetermined reduction ratio and multiple images having stepwise resolutions are generated. Then, a feature point and a local feature amount are extracted from the multiple images. The feature points and the local feature amounts thus extracted from the multiple images generated in such a manner are collectively utilized. Thus, even when images before and after reduction are compared with each other, it can be determined that similarity is high.
When a combination of feature points is determined between two images, if only a local feature amount about which two feature points show similarity is selected as described above, an erroneous combination may occur. (Refer to combination 733 in FIG. 7) This erroneous combination also affects determination of other combinations and reduces comparison accuracy.